package com.wc.alorithm_blue_bridge._数学知识.约数.既约分数;

/**
 * @Author congge
 * @Date 2023/10/11 12:04
 * @description 既约分数
 * https://www.lanqiao.cn/problems/593/learning/?page=2&first_category_id=1&sort=students_count&second_category_id=3
 */
public class Main {
    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int num1 = sc.nextInt();
//        int num2 = sc.nextInt();
        int num1;
        int num2;
//        Main main = new Main();
//        System.out.println(main.gcd(num1, num2));
        int ans = 0;
        Main main = new Main();
        for (int i = 1; i <= 2020; i++) {
            for (int j = 1; j <= 2020; j++) {
                num1 = i;
                num2 = j;
                if (main.gcd(num1, num2) == 1) {
                    ans++;
                }
            }
        }

        System.out.println(ans);
    }

    /**
     * 辗转相除法
     *
     * @param num1
     * @param num2
     * @return
     */
    public int gcd(int num1, int num2) {
        if (num1 > num2) {
            return gcd(num2, num1);
        }

        while (num2 % num1 != 0) {
            num2 = num2 % num1;
            num2 = num1 + num2;
            num1 = num2 - num1;
            num2 = num2 - num1;
        }
        return num1;
    }
}
